package aSortModel;

public class Heap_sort extends Object{
    public int[] heap_sort(int[] arr){
        /**
         * 构造大根堆
         * 交换结点调整
         */
        int len = arr.length;
        //从最后一个叶子结点的父节点开始调整为大根堆
        for(int i = len/2-1;i>=0;i--){
            adjust(arr,len,i);
        }

        //0 结点和1之后的每一个结点作交换
        for(int i = len-1;i>0;i--){
            int buff = arr[0];
            arr[0] = arr[i];
            arr[i] = buff;
            //忽略掉最后一个结点的调整
            adjust(arr,i,0);
        }
        return arr;
    }

    public void adjust(int[] arr,int len,int rootIndex){
        int l = rootIndex*2+1;
        int r = rootIndex*2+2;
        int maxIndex = rootIndex;
        if(l<len && arr[l]>arr[maxIndex]) maxIndex = l;
        if(r<len && arr[r]>arr[maxIndex]) maxIndex = r;

        if(maxIndex!=rootIndex){
            int buff = arr[maxIndex];
            arr[maxIndex] = arr[rootIndex];
            arr[rootIndex] = buff;
            adjust(arr,len,maxIndex);
        }
    }

    public static void main(String[] args) {
        for (int i : new Heap_sort().heap_sort(new int[]{5, 2, 9, 7, 1, 6, 4})) {
            System.out.println(i);
        }
    }
}
